package ikelib;
import java.text.*;

public class Fourier {

	// Main Routine
	public static void execute(boolean inverse, Field[] f, Field[] new_f) {
		int n = f.length;
		int n2 = n >> 1;
		Field[] wtbl = f[0].make_wtbl(n);

		Field t = f[0].copy();

		for(int i=0; i<n; i++) {
			new_f[i].setZero();
			for(int k=0; k<n; k++) {
				int a = (inverse) ? (i*k)%n : (-i*k+n*n)%n;
				boolean neg = false;
				if(a > n2) {a -= n2; neg = true;}
				t.set(f[k]).timesBy(wtbl[a]);
				if(neg) t.negate();
				new_f[i].addTo(t);
			}
		}

		if(! inverse)
			for(int i=0; i<n; i++) new_f[i].div(n);
	}

	// Sample Data
	public static void main(String[] args) {
		int N = 40;
		Field[] z1 = new Field[N];
		Field[] z2 = new Field[N];
		Field[] z3 = new Field[N];

		for(int i=0; i<N; i++) {
			double re = 6 * Math.cos( 6 * Math.PI * i / N) + 4 * Math.sin(18 * Math.PI * i / N);
			z1[i] = new Complex(re, 0);
			z2[i] = new Complex(0, 0);
			z3[i] = new Complex(0, 0);
		}

		Fourier.execute(false, z1, z2); // Fourier

		Fourier.execute(true, z2, z3); // InverseFourier

		DecimalFormat df = new DecimalFormat();
		df.setMinimumIntegerDigits(2);

		System.out.println("     |  Sample Data  |  Fourier      |  InverseFourier");
		for(int i=0; i<N; i++) {
			StringBuffer sb = new StringBuffer();
			sb.append("  ");
			sb.append(df.format(i));
			sb.append(" | ");
			sb.append(z1[i]);
			sb.append(" | ");
			sb.append(z2[i]);
			sb.append(" | ");
			sb.append(z3[i]);
			System.out.println(sb.toString());
		}
	}

}
/*
     |  Sample Data  |  Fourier      |  InverseFourier
  00 |  6.000  0.000 | -0.000  0.000 |  6.000 -0.000
  01 |  9.297  0.000 | -0.000 -0.000 |  9.297 -0.000
  02 |  4.763  0.000 |  0.000 -0.000 |  4.763 -0.000
  03 | -2.625  0.000 |  3.000  0.000 | -2.625  0.000
  04 | -4.205  0.000 |  0.000 -0.000 | -4.205  0.000
  05 | -1.414  0.000 |  0.000  0.000 | -1.414 -0.000
  06 | -2.470  0.000 | -0.000  0.000 | -2.470  0.000
  07 | -7.742  0.000 |  0.000 -0.000 | -7.742  0.000
  08 | -8.658  0.000 |  0.000  0.000 | -8.658  0.000
  09 | -2.098  0.000 |  0.000 -2.000 | -2.098 -0.000
  10 |  4.000  0.000 | -0.000  0.000 |  4.000 -0.000
  11 |  3.350  0.000 | -0.000 -0.000 |  3.350 -0.000
  12 |  1.050  0.000 |  0.000  0.000 |  1.050 -0.000
  13 |  4.110  0.000 |  0.000 -0.000 |  4.110  0.000
  14 |  8.942  0.000 | -0.000  0.000 |  8.942  0.000
  15 |  7.071  0.000 | -0.000  0.000 |  7.071  0.000
  16 | -0.497  0.000 | -0.000  0.000 | -0.497  0.000
  17 | -4.503  0.000 | -0.000  0.000 | -4.503  0.000
  18 | -2.291  0.000 | -0.000 -0.000 | -2.291  0.000
  19 | -1.395  0.000 | -0.000  0.000 | -1.395 -0.000
  20 | -6.000  0.000 | -0.000  0.000 | -6.000  0.000
  21 | -9.297  0.000 | -0.000 -0.000 | -9.297  0.000
  22 | -4.763  0.000 | -0.000  0.000 | -4.763  0.000
  23 |  2.625  0.000 | -0.000 -0.000 |  2.625 -0.000
  24 |  4.205  0.000 | -0.000 -0.000 |  4.205 -0.000
  25 |  1.414  0.000 | -0.000 -0.000 |  1.414 -0.000
  26 |  2.470  0.000 | -0.000  0.000 |  2.470  0.000
  27 |  7.742  0.000 |  0.000  0.000 |  7.742 -0.000
  28 |  8.658  0.000 |  0.000 -0.000 |  8.658 -0.000
  29 |  2.098  0.000 | -0.000  0.000 |  2.098 -0.000
  30 | -4.000  0.000 | -0.000 -0.000 | -4.000 -0.000
  31 | -3.350  0.000 |  0.000  2.000 | -3.350 -0.000
  32 | -1.050  0.000 |  0.000 -0.000 | -1.050  0.000
  33 | -4.110  0.000 |  0.000  0.000 | -4.110  0.000
  34 | -8.942  0.000 | -0.000 -0.000 | -8.942 -0.000
  35 | -7.071  0.000 |  0.000 -0.000 | -7.071  0.000
  36 |  0.497  0.000 |  0.000  0.000 |  0.497  0.000
  37 |  4.503  0.000 |  3.000 -0.000 |  4.503 -0.000
  38 |  2.291  0.000 |  0.000  0.000 |  2.291 -0.000
  39 |  1.395  0.000 | -0.000  0.000 |  1.395  0.000
*/
